package org.blogwu.learn.leetcode.二叉树;

import org.blogwu.learn.algorithm.树.二叉搜索树.printer.BinaryTreeInfo;

public class TreeNode implements BinaryTreeInfo {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    static TreeNode root;


    public static TreeNode convert(Integer[] array) {
        int floor = 0, count = 0;
        TreeNode[] treeNodes = new TreeNode[array.length];
        while (array != null && count < array.length) {
            int start = (int) Math.pow(2, floor) - 1;
            int end = (int) Math.pow(2, floor + 1) - 1;
            if (end > array.length) {
                end = array.length;
            }
            for (int i = start; i < end; i++) {
                if (array[i] != null) {
                    treeNodes[i] = new TreeNode(array[i]);
                } else {
                    treeNodes[i] = null;
                }
                if (i > 0) {
                    int parent = (i - 1) / 2;
                    if (parent >= 0) {
                        TreeNode pNode = treeNodes[parent];
                        if (pNode != null) {
                            if (i % 2 == 1) {
                                pNode.left = treeNodes[i];
                            } else {
                                pNode.right = treeNodes[i];
                            }
                        }
                    }
                }
                count++;
            }
            floor++;
        }
        TreeNode.root = treeNodes[0];
        return treeNodes[0];
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((TreeNode) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((TreeNode) node).right;
    }

    @Override
    public Object string(Object node) {
//        TreeNode myNode = (TreeNode) node;
//        String parentString = "null";
//        if (myNode.parent != null) {
//            parentString = myNode.parent.element.toString();
//        }
//        return myNode.element + "_p(" + parentString + ")";
        return ((TreeNode) node).val;
    }


    /**
     * 添加元素
     */
    public void add(int val) {
        // 初始化根节点
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        // 非第一个节点
        TreeNode node = root;
        TreeNode parent = root;
        int cmp = 0;
        // 一直遍历
        while (node != null) {
            cmp = val - node.val;
            // 保存父节点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {  // 相等
                node.val = val;
                return;
            }
        }
        // 插入节点
        TreeNode newNode = new TreeNode(val);
        // 保存父节点
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
    }

    public TreeNode getRoot() {
        return root;
    }

    public TreeNode() {
    }
}
